﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Grafos {
    /// <summary>
    /// Representa um passeio qualquer em um grafo
    /// </summary>
    /// <remarks>
    /// Não garante ser trilha (sem repetição de arestas) ou caminho (sem repetição de vértices)
    /// Não garante que o passeio desenhado seja possível (vértices vizinhos)
    /// </remarks>
    public class Passeio : ICloneable {

        private List<Vértice> passeio;

        /// <summary>
        /// Último vértice do passeio
        /// </summary>
        public Vértice ÚltimoVértice {
            get {
                if (passeio.Count == 0)
                    return null;
                return passeio[passeio.Count - 1];
            }
        }

        /// <summary>
        /// Diz se o passeio é um ciclo
        /// </summary>
        /// <remarks>
        /// Passeios são ciclos quando terminam onde começam
        /// </remarks>
        public bool Ciclo {
            get {
                if (passeio.Count == 0)
                    return false;
                return passeio[0] == ÚltimoVértice;
            }
        }

        /// <summary>
        /// Diz quantos vértices há no passeio
        /// </summary>
        public int QuantidadeVértices {
            get {
                return passeio.Count;
            }
        }

        /// <summary>
        /// Instancia um novo passeio vazio
        /// </summary>
        public Passeio() {
            passeio = new List<Vértice>();
        }

        /// <summary>
        /// Adiciona um novo vértice ao passeio
        /// </summary>
        /// <param name="v">Vértice do passeio</param>
        /// <remarks>
        /// Este novo vértice será adicionado ao fim do passeio
        /// </remarks>
        public void AdicionarVértice(Vértice v) {
            passeio.Add(v);
        }

        /// <summary>
        /// Adiciona uma coleção de vértices ao passeio
        /// </summary>
        /// <param name="g">Grafo que contém os vértices</param>
        /// <param name="nomes">Lista dos vértices (em ordem) para serem adicionados</param>
        /// <remarks>
        /// Os vértices serão adicionados na ordem do vetor
        /// </remarks>
        public void AdicionarVértice(Grafo g, params string[] nomes) {
            foreach (string s in nomes) {
                passeio.Add(g.BuscarVértice(s));
            }
        }

        /// <summary>
        /// Diz se o passeio contém o vértice dado
        /// </summary>
        /// <param name="v">Vértice a ser procurado</param>
        /// <returns>True caso o passeio possua o vértice, False caso contrário</returns>
        public bool Possui(Vértice v) {
            return passeio.Contains(v);
        }

        /// <summary>
        /// Diz qual o vértice seguinte a um determinado vértice
        /// </summary>
        /// <param name="v">Vértice a ser procurado</param>
        /// <returns>Vértice imediatamente após o vértice procurado, ou null se não houver</returns>
        public Vértice Próximo(Vértice v) {
            return Próximo(Posição(v));
        }

        /// <summary>
        /// Diz qual o vértice seguinte à posição dada
        /// </summary>
        /// <param name="pos">Posição de um vértice no passeio</param>
        /// <returns>Vértice seguinte ao vértice ao vértice no dado índice, ou null se não houver</returns>
        public Vértice Próximo(int pos) {
            Vértice ret;
            if (pos == -1)
                ret = null;
            else if (pos == passeio.Count - 1)
                ret = passeio[0];
            else
                ret = passeio[pos + 1];

            return ret;
        }
        
        /// <summary>
        /// Procura um vértice no caminho e diz sua posição
        /// </summary>
        /// <param name="v">Vértice a ser procurado</param>
        /// <returns>Índice do vértice, -1 se não houver</returns>
        public int Posição(Vértice v) {
            return passeio.IndexOf(v);
        }

        /// <summary>
        /// Operação de torção, utilizado nos algoritmos K-opt
        /// </summary>
        /// <param name="i">Vértice do início da torção</param>
        /// <param name="j">Vértice do fim da torção</param>
        public void Torcer(Vértice i, Vértice j) {
            int indexI, indexJ;

            indexI = Posição(i);
            indexJ = Posição(j);

            Revert(indexI, indexJ);
        }

        /// <summary>
        /// Operação de torção, utilizado nos algoritmos K-opt
        /// </summary>
        /// <param name="i">Início da torção</param>
        /// <param name="j">Fim da torção</param>
        public void Torcer(int i, int j) {
            Revert(i, j);
        }

        /// <summary>
        /// Cria uma cópia do passeio
        /// </summary>
        /// <returns>Retorna um array de vértices, em ordem de passeio</returns>
        public Vértice[] Listar() {
            return passeio.ToArray();
        }

        /// <summary>
        /// Retorna uma cópia profunda deste passeio
        /// </summary>
        /// <returns></returns>
        public object Clone() {
            Passeio p = new Passeio();
            foreach (Vértice v in passeio)
                p.AdicionarVértice(v);
            return p;
        }

        /// <summary>
        /// Calcula o valor total do passeio
        /// </summary>
        /// <returns>Valor numérico que é a soma de cada aresta do passeio</returns>
        public float Valor() {
            int i;
            float w = 0;

            for (i = 0; i < QuantidadeVértices - 1; i++) {
                w += ((ArestaPonderada)passeio[i].ProcurarAresta(passeio[i + 1])).Valor;
            }

            return w;
        }

        /// <summary>
        /// Converte o passeio para um literal, com o nome dos vértices em lista
        /// </summary>
        /// <returns></returns>
        public override string ToString() {
            StringBuilder sb = new StringBuilder();

            foreach (Vértice v in passeio) {
                sb.Append(v.Nome);
                sb.Append(", ");
            }
            sb = sb.Remove(sb.Length - 2, 2);

            return sb.ToString();
        }

        /// <summary>
        /// Inverte um determinado trecho do caminho (utilizado na torção)
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        private void Revert(int start, int end) {
            Vértice temp;

            while (start < end) {
                temp = passeio[start];
                passeio[start] = passeio[end];
                passeio[end] = temp;
                start++;
                end--;
            }
        }
    }
}
